\section{A Distributed Computing Model for Big Data}

In this section we introduce our {distributed big data model}.
We consider a network of $k$ distinct machines $N = \{p_1,\dots,p_k\}$ 
that are pairwise connected by bidirectional point-to-point communication links.
Each machine executes an instance of a distributed algorithm $A$.
The computation advances in synchronous rounds where, in each round,
machines can exchange messages over their communication links.
Since we are interested in scalable algorithms, we limit the communication between any two machines to $B$ bits per round round, which corresponds to the standard CONGEST model (cf.\ \cite{peleg}).
We assume that local computation, on the other hand, happens instantaneously in zero time, which is motivated by its much lower cost compared to inter-machine communication.
Note that machines have no other means of communication and do not share any
memory.

We are interested in solving graph problems where we are given an \emph{input graph} $G$ of $n$ vertices and $m$ edges from some \emph{input domain} $\cG$.
Initially, the entire graph $G$ is not known by a single machine, but rather partitioned among the local state of the machines in $N$, as we explain in more detail in Sec. TODO.\peter{We don't want to make the random partitioning part of the model, right?}
Depending on $P$, the vertices and/or edges of $G$ have labels chosen from a set of polynomial (in $n$) size.
Eventually, each machine must (irrevocably) set a designated local output variable $o_i$ and the \emph{output configuration} $o=\langle o_1,\dots,o_k\rangle$ must satisfy certain feasibility conditions w.r.t.\ problem $P$.
For example, when considering the MST problem, each $o_i$ corresponds to a set of edges and the edges in the union of the sets $o_i$ must form an MST of the input graph $G$.
We say that \emph{algorithm $A$ solves problem $P$} if $A$ maps each $G\in \cG$ to an output configuration that is feasible for $P$.

The \emph{time complexity of $A$} is the maximum number of rounds until termination, over all graphs in $\cG$.


\endinput
